In some applications, a storage system can provide storage to a virtual machine (“VM”) running in a virtualization environment on a host system connected to the storage system. Examples of such storage systems include the storage systems produced by EMC Corporation of Massachusetts. The storage system can make a logical storage device (e.g., a virtual volume) available to the VM, such that the VM can read data from and write data to the logical storage device. The VM can use the logical storage device as, for example, a configuration device, a swap device, or a data device. The storage for the logical storage device can be provisioned from one or more of the physical storage devices (e.g., magnetic disk drives, solid state drives (“SSDs”), etc.) of the storage system, and the storage system can manage on which physical storage devices data from the logical storage device are stored in a manner transparent to the VM. Conventional approaches to provisioning storage for logical storage devices can lead to inefficient resource utilization or failure to provision any space for the logical storage device.